package com.qch.edu.Tree.DiguiTaolu;

/**
 * @Author qch
 * @Date 2021/3/13
 * 题目：给定以课二叉树的头节点head（X）,返回满足搜索二叉树的子树的头部节点
 * 1）与X无关 选择左树满足搜索二叉树的子树
 * 2）与X有关 左树是搜索二叉树
 *             右树是搜索二叉树
 *             左树最大值小于X
 *             右树最小值大于X
 *
 * * 以X为头的节点
 *  * 潜在信息：左子树信息和右子树信息可以得到
 *
 *  搜索二叉树：节点内容没有重复，且以X为头，左树小，右树大
 */
public class SearchTree {
    public static class Node {
        private int value;        //节点的值
        private Node node;        //此节点，数据类型为Node
        private Node left;        //此节点的左子节点，数据类型为Node
        private Node right;       //此节点的右子节点，数据类型为Node
        public Node(int data){
            this.value=data;
        }
    }
    public static class Info{
        //注意：如果左树整体就是搜索二叉树，那满足搜索二叉树的子树就变成整颗左树大小
        public int maxSubBSTSize;//满足搜索二叉树的最大值
        public boolean isAllBst;//是否是搜索二叉树
        public int max;//整棵树最小值
        public int min;

        public Info(int maxSubBSTSize, boolean isAllBst, int max, int min) {
            this.maxSubBSTSize = maxSubBSTSize;
            this.isAllBst = isAllBst;
            this.max = max;
            this.min = min;
        }

    }
    public static Info process(Node X){
        if (X==null)
        {
            return null;
        }
        Info leftInfo = process(X.left);
        Info rightInfo = process(X.right);

        int max=X.value;//整棵树最小值
        int min=X.value;
        if (leftInfo!=null){
            min=Math.min(min,leftInfo.min);
            max=Math.max(max,leftInfo.max);
        }
        if (rightInfo!=null){
            min=Math.min(min,rightInfo.min);
            max=Math.max(max,rightInfo.max);
        }
        int maxSubBSTSize=0;//满足搜索二叉树的最大值
        if(leftInfo!=null)
        {
            maxSubBSTSize=leftInfo.maxSubBSTSize;
        }
        if(rightInfo!=null)
        {
            maxSubBSTSize=Math.max(maxSubBSTSize,rightInfo.maxSubBSTSize);
        }
        boolean isAllBst=false;//是否是搜索二叉树
        if(
                //如果可能性2成立
                //与X有关 左树是搜索二叉树
                //             右树是搜索二叉树
                //            左树最大值小于X
                //    右树最小值大于X
                ( leftInfo==null?true:leftInfo.isAllBst)
                &&( rightInfo==null?true:rightInfo.isAllBst)
                &&(leftInfo==null?true:leftInfo.max<X.value)
                &&(rightInfo==null?true:rightInfo.min>X.value)
                ){
            maxSubBSTSize= ( leftInfo==null?0:leftInfo.maxSubBSTSize)+( rightInfo==null?0:rightInfo.maxSubBSTSize)+1;//以X为头的所有节点数；
            isAllBst=true;
        }
        return new Info( maxSubBSTSize,  isAllBst,  max,  min);
    }

    public static boolean isBalance2(Node head){
        return process(head).isAllBst;
    }
    public static void main(String[] args) {

    }
}
